<?php

class Solution
{

    /**
     * @param $str
     * @return Boolean
     */
    function isValid($str)
    {
        $symbols = ["(" => ")", "[" => "]", "{" => "}"];

        $result = true;
        $stack = array();

        for ($i = 0, $iMax = strlen($str); $i < $iMax; $i++) {
            if (array_key_exists($str[$i], $symbols)) {
                //左括号  把对应的右括号进栈
                $stack[] = $symbols[$str[$i]];
            } elseif (in_array($str[$i], array_values(($symbols)))) {
                //右括号，从栈里pop 判断是不是匹配
                if (!empty($stack)) {
                    if ($str[$i] !== array_pop($stack)) {
                        $result = false;
                        break;
                    }
                } else {
                    $result = false;
                    break;
                }
            }
        }

        if (empty($stack)) {
            return $result;
        } else {
            return false;
        }
    }
}
